googologywikiaorg-20200223-history
User blog:P進大好きbot/Cheatsheet on Properties of OCFs
I list significant properties, e.g. typical expansions of standard expressions of ordinals, of several OCFs which are helpful in analysis. I am not good at explicit computation, and hence tables below might contain many errors. For an ordinal \(\alpha\), I denote by \(\alphan\) a fixed choice of a fundamental sequence of \(\alpha\), i.e. a strictly increasing map \(\textrm{cof}(\alpha) \to \alpha, \ n \mapsto \alphan\) above whose image \(\alpha\) is the least ordinal. = Buchholz's OCF = References: # W. Buchholz, A new system of proof-theoretic ordinal functions, Annals of Pure and Applied Logic, Volume 32 (1986), pp. 195--207. # W. Buchholz, Relating ordinals to proofs in a prespicious way, unpublished article. # Buchholz's function, wiki article. I list characters in standard expressions with respect to Buchholz's \(\psi\). I list standard expressions of specific ordinals with respect to Buchholz's \(\psi\), which will be used in order to define the conventional notion of a semi-standard expression. I call an expression of an ordinal semi-standard if the expression given by replacing all the occurence of \(1\) and \(\omega\) which are not indices of \(\psi\) in it by \(\psi_0(0)\) and \(\psi_0(\psi_0(0))\) respectively is standard with respect to Buchholz's \(\psi\). I list semi-standard expressions of specific ordinals with respect to Buchholz's \(\psi\). I list non-semi-standard expressions of ordinals with respect to Buchholz's \(\psi\). I list nest-free expansions of semi-standard expressions of ordinals with respect to Buchholz's \(\psi\). I list nesting expansions of standard expressions of countable ordinals with respect to Buchholz's \(\psi\). = Extended Buchholz's OCF = References: # D. Maksudov, The extension of Buchholz's function, Traveling To The Infinity. # Buchholz's function#Extension, wiki article. I list characters in standard expressions with respect to extended Buchholz' \(\psi\). I list standard expressions of specific ordinals with respect to extended Buchholz's \(\psi\), which will be used in order to define the conventional notion of a semi-standard expression. I call an expression of an ordinal semi-standard if the expression given by replacing all the occurence of \(1\) and \(\omega\) in it by \(\psi_0(0)\) and \(\psi_0(\psi_0(0))\) respectively is standard with respect to extended Buchholz's \(\psi\). I list semi-standard expressions of specific ordinals with respect to extended Buchholz's \(\psi\). I list non-semi-standard expressions of ordinals with respect to extended Buchholz's \(\psi\). I list nest-free expansions of semi-standard expressions of ordinals with respect to extended Buchholz's \(\psi\). I list nesting expansions of semi-standard expressions of countable ordinals with respect to extended Buchholz's \(\psi\). Since extended Buchholz's OCF restricted to \(\varepsilon_{\Omega_{\omega}+1}\) coincides with Buchholz's OCF, I only list expansions of ordinals greater than or equal to \(\psi_0(\varepsilon_{\Omega_{\omega}+1}) = \psi_0(\psi_{\omega+1}(0))\) in extended Buchholz's \(\psi_0\). = Rathjen's OCF Based on a Weakly Mahlo Cardinal = References: # M. Rathjen, Ordinal Notations Based on a Weakly Mahlo Cardinal, Archive for Mathematical Logic, Volume 29, Issue 4 (1990), pp. 249--263. # Ordinal notation#Rathjen's ψ, wiki article. I deal with Rathjen's weakly Mahlo \(\psi\), i.e. Rathjen's \(\psi\) based on the least weakly Mahlo cardinal \(M\) with a specific ordinal notation system introduced in the first reference above. I note that it does not coincide with the simplified OCF introduced in The Realm of Ordinal Analysis without a specific associated ordinal notation system, and is not a formal symbol in the ordinal notation system introduced in Proof-Theoretic Analysis of KPM. Be careful that many googologists compfound them, because they sometimes talk about Rathjen's \(\psi\) even though many of them have not even take a brief look at the precise definition. I list characters in standard expressions with respect to Rathjen's weakly Mahlo \(\psi\). I list standard expressions of specific ordinals with respect to Rathjen's weakly Mahlo \(\psi\), which will be used in order to define the conventional notion of a semi-standard expression. I call an expression of an ordinal semi-standard if the expression given by replacing all the occurence of \(1\), \(2\), \(3\), \(\omega\), \(\Omega\), \(\Omega_2\), \(\Omega_3\), \(I\), \(I_2\), and \(I_3\) by \(\varphi_{0}(0)\), \(\varphi_{0}(0)+\varphi_{0}(0)\), \(\varphi_{0}(0)+\varphi_{0}(0)+\varphi_{0}(0)\), \(\varphi_{0}(\varphi_{0}(0))\), \(\chi_{0}(0)\), \(\chi_{0}(\varphi_{0}(0))\), \(\chi_{0}(\varphi_{0}(0)+\varphi_{0}(0))\), \(\chi_{\varphi_{0}(0)}(0)\), \(\chi_{\varphi_{0}(0)}(\varphi_{0}(0))\), and \(\chi_{\varphi_{0}(0)}(\varphi_{0}(0)+\varphi_{0}(0))\) respectively is standard. I list semi-standard expressions of specific ordinals with respect to Rathjen's weakly Mahlo \(\psi\). I list expressions of specific ordinals using multiplications and powers, which are not characters which are allowed to appear in semi-standard expressions with respect to Rathjen's weakly Mahlo \(\psi\). Since the definition is complicated, the table might contain descriptions which lack necessary restrictions. I list non-standard expressions of ordinals with respect to Rathjen's weakly Mahlo \(\psi\). I list nest-free expansions of semi-standard expressions of ordinals with respect to Rathjen's weakly Mahlo \(\psi\). I list nesting expansions of semi-standard expressions of countable ordinals with respect to Rathjen's weakly Mahlo \(\psi\). * Below \(\psi_{\Omega}(\psi_{\Omega_2}(0))\) * Below \(\psi_{\Omega}(\Phi_{1}(0))\) * Below \(\psi_{\Omega}(\psi_{I}(0))\) * Below \(\psi_{\Omega}(\psi_{\chi_{2}(0)}(0))\) * Below \(\psi_{\Omega}(\psi_{\chi_{M}(0)}(0))\) * Below \(\psi_{\Omega}(\chi_{M}(0))\) * Below \(\psi_{\Omega}(\psi_{\chi_{M+M}(0)}(0))\) * Below \(\psi_{\Omega}(\psi_{\chi_{\varphi_{1}(M+1)}(0)}(0))\) I note that the countable limit of Rathjen's weakly Mahlo \(\psi\) itself is \(\sup \{\psi_{\Omega}(\alpha) \mid \alpha < \Gamma_{M+1}\}\), which is much greater than \(\psi_{\Omega}(\psi_{\chi_{\varphi_{1}(M+1)}(0)}(0))\). On the other hand, the ordinal notation system \(T(M)\) associated to Rathjen's weakly Mahlo \(\psi\) satisfies \(T(M) \cap M = C_{\Omega}(\psi_{\chi_{\varphi_{1}(M+1)}(0)}(0)) \cap \psi_{\chi_{\varphi_{1}(M+1)}(0)}(0)\) by Theorem 6.3 in the first reference. It means that the recursive interpretation of the \(\in\)-relation on ordinals associated to Rathjen's weakly Mahlo \(\psi\) might not be applicable to countable ordinals above \(\psi_{\Omega}(\psi_{\chi_{\varphi_{1}(M+1)}(0)}(0))\). Namely, any "analysis" on Rathjen's weakly Mahlo \(\psi\) above \(\psi_{\Omega}(\psi_{\chi_{\varphi_{1}(M+1)}(0)}(0))\) is not based on an actual algorithm to determine fundamental sequences, and hence is not reproducible. Honestly, I do not even know whether the \(\in\)-relation is decidable or not in the whole system of countable ordinals describable by Rathjen's weakly Mahlo \(\psi\) with respect to the obvious extension of the coding given in Definition 6.1 in the first reference. Therefore it is quite reasonable to stop here. = Rathjen's OCF Based on a Weakly Compact Cardinal = References: # M. Rathjen, Proof Theory of Reflection, Annals of Pure and Applied Logic, Volume 68, Issue 2 (1994), pp. 181--224. I deal with Rathjen's weakly compact \(\Psi\), i.e. Rathjen's \(\Psi\) based on the least weakly compact cardinal \(K\) with a specific ordinal notation system introduced in the reference above. I list characters in standard expressions with respect to Rathjen's weakly compact \(\Psi\). I list expansions of ordinals in Rathjen's weakly compact \(\Psi\). WIP = Arai's OCF = References: # T. Arai, A Simplified Ordinal Analysis of First-Order Reflection, preprint in arXiv. I list expansions of ordinals in Arai's \(\psi_{\Omega_1}\) based on the least \(\Pi^1_{N-2}\)-indescribable cardinal \(\mathbb{N}\) for a fixed \(N \in \mathbb{N}\) greater than \(2\). WIP Category:Blog posts